A centralized Unified Messaging Voice Mail system includes a Unified Messaging server and several protocol converters coupled via a wide area network (WAN). Typically, the Unified Messaging server is located at a data center and the protocol converters are located at respective branch offices. Each protocol converter provides protocol conversion between circuit-switched phone calls from the branch office telephone switch (e.g., PBX) and Voice over IP (VoIP) VoIP protocols over the IP network. A problem with typical Unified Messaging Voice Mail systems is that a call will not be answered if the WAN is unavailable at the time the gateway receives the call.